Navigation systems for vehicles require a digital map of the road network for the main functions of position finding, destination selection, route calculation, and destination guiding. This digital road map is usually provided on a digital storage medium, such as a CD, DVD, or SD card. The data representing the digital road map are housed in files on the storage medium. The data are provided in a linear sequence in the file.
The navigation system requires these data to show the map of a road network on a display screen or to project the current position on a nearest road of the road network, for example. The current position may be determined, for example, using GPS (global positioning system) or Galileo and/or further inertial sensors, such as odometers, rotational speed sensors, or acceleration meters.
In many applications of the navigation system, large parts of the overall road network stored on the storage medium play no role or only a subordinate role. For example, a concrete destination route guide may be restricted to a regional area, although the road network of an entire country is stored. It is also conceivable that the user will want to have an enlarged detail of his current position displayed.
If all roads within a two-dimensional search area are searched in a linearly stored digital road map, the entire road map must be searched through, which is connected to significant time expenditure. In addition, the information content of digital road maps increases continuously; on the one hand, individual roads are broken down into shorter and shorter road sections, on the other hand, additional information is incorporated, such as geographic locations of fuel stations or so-called points of interest (POI). The time expenditure necessary for searching through the road map may result in a delayed display, which is annoying to a user.
To avoid completely searching through the road map in such cases, the roads contained in the digital road maps are structured.
Combining adjacent roads into an information unit, a so-called cluster, is known. City areas, city limits, district limits, or similar geographic boundaries are used for orientation. Adjacent clusters are combined into hierarchically higher clusters. This procedure is continued for higher levels. A relatively well-balanced, hierarchical tree arises as a result. For the tree not to become excessively large, roads are stored linearly and sorted geometrically on the lowermost level. Typical numbers on this level are approximately 1,000 roads.
In a further known structuring, the digitized road network has a uniform raster superimposed, which includes a plurality of equal rectangles, the so-called tiles. All roads which lie in a tile are stored together. An index is applied to the storage medium, which assigns geographic coordinates to the tiles, so that the tile may be rapidly accessed from a coordinate via the index. This has the disadvantage, however, that the tiles are populated with roads very differently; some tiles contain a very large number of roads, while others contain no or only a few roads, in contrast. The storage is thus ineffective and the time required for a search is very dependent on the location of the search area.